<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>快速排序算法详解</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
        }
        .serif-font {
            font-family: 'Noto Serif SC', serif;
        }
        .gradient-bg {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .code-container {
            background: #1e1e1e;
            border-radius: 12px;
            overflow: hidden;
        }
        .code-header {
            background: #2d2d2d;
            padding: 12px 20px;
            display: flex;
            align-items: center;
            justify-content: space-between;
        }
        .code-dots {
            display: flex;
            gap: 8px;
        }
        .dot {
            width: 12px;
            height: 12px;
            border-radius: 50%;
        }
        .dot-red { background: #ff5f56; }
        .dot-yellow { background: #ffbd2e; }
        .dot-green { background: #27c93f; }
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
        }
        code {
            font-family: 'Consolas', 'Monaco', 'Courier New', monospace;
            font-size: 14px;
            line-height: 1.6;
            color: #d4d4d4;
        }
        .keyword { color: #569cd6; }
        .type { color: #4ec9b0; }
        .function { color: #dcdcaa; }
        .string { color: #ce9178; }
        .comment { color: #6a9955; }
        .number { color: #b5cea8; }
        .hover-card {
            transition: all 0.3s ease;
        }
        .hover-card:hover {
            transform: translateY(-4px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        .first-letter::first-letter {
            font-size: 3.5rem;
            font-weight: 700;
            float: left;
            line-height: 1;
            margin-right: 0.5rem;
            color: #667eea;
        }
        @keyframes fadeIn {
            from { opacity: 0; transform: translateY(20px); }
            to { opacity: 1; transform: translateY(0); }
        }
        .fade-in {
            animation: fadeIn 0.8s ease-out;
        }
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="gradient-bg text-white py-20 px-6">
        <div class="max-w-6xl mx-auto text-center fade-in">
            <h1 class="text-5xl md:text-6xl font-bold mb-6 serif-font">快速排序算法</h1>
            <p class="text-xl md:text-2xl opacity-90 max-w-3xl mx-auto">
                分治思想的经典体现，平均时间复杂度 O(n log n) 的高效排序算法
            </p>
            <div class="mt-10 flex justify-center gap-8">
                <div class="text-center">
                    <i class="fas fa-bolt text-4xl mb-2"></i>
                    <p class="text-sm">高效快速</p>
                </div>
                <div class="text-center">
                    <i class="fas fa-code-branch text-4xl mb-2"></i>
                    <p class="text-sm">分治策略</p>
                </div>
                <div class="text-center">
                    <i class="fas fa-memory text-4xl mb-2"></i>
                    <p class="text-sm">原地排序</p>
                </div>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-6xl mx-auto px-6 py-16">
        <!-- 算法概述 -->
        <section class="mb-16 fade-in">
            <div class="bg-white rounded-2xl shadow-lg p-8 hover-card">
                <h2 class="text-3xl font-bold mb-6 text-gray-800 flex items-center">
                    <i class="fas fa-info-circle text-purple-600 mr-3"></i>
                    算法概述
                </h2>
                <div class="prose prose-lg max-w-none">
                    <p class="text-gray-700 leading-relaxed first-letter">
                        快速排序是一种高效的排序算法，采用分治法策略。它通过选择一个"基准"元素，将数组分为两个子数组，一个包含小于基准的元素，另一个包含大于基准的元素，然后递归地排序这两个子数组。
                    </p>
                </div>
            </div>
        </section>

        <!-- 核心特性 -->
        <section class="mb-16 fade-in">
            <h2 class="text-3xl font-bold mb-8 text-center text-gray-800">核心特性</h2>
            <div class="grid md:grid-cols-3 gap-6">
                <div class="bg-white rounded-xl shadow-md p-6 hover-card">
                    <div class="text-purple-600 text-3xl mb-4">
                        <i class="fas fa-tachometer-alt"></i>
                    </div>
                    <h3 class="text-xl font-semibold mb-3">时间复杂度</h3>
                    <p class="text-gray-600">平均情况：O(n log n)</p>
                    <p class="text-gray-600">最坏情况：O(n²)</p>
                    <p class="text-gray-600">最好情况：O(n log n)</p>
                </div>
                <div class="bg-white rounded-xl shadow-md p-6 hover-card">
                    <div class="text-purple-600 text-3xl mb-4">
                        <i class="fas fa-database"></i>
                    </div>
                    <h3 class="text-xl font-semibold mb-3">空间复杂度</h3>
                    <p class="text-gray-600">O(log n) - 递归调用栈</p>
                    <p class="text-gray-600">原地排序算法</p>
                    <p class="text-gray-600">不需要额外数组空间</p>
                </div>
                <div class="bg-white rounded-xl shadow-md p-6 hover-card">
                    <div class="text-purple-600 text-3xl mb-4">
                        <i class="fas fa-cogs"></i>
                    </div>
                    <h3 class="text-xl font-semibold mb-3">算法特点</h3>
                    <p class="text-gray-600">不稳定排序</p>
                    <p class="text-gray-600">分治策略</p>
                    <p class="text-gray-600">适合大数据集</p>
                </div>
            </div>
        </section>

        <!-- 算法流程图 -->
        <section class="mb-16 fade-in">
            <div class="bg-white rounded-2xl shadow-lg p-8">
                <h2 class="text-3xl font-bold mb-6 text-gray-800 flex items-center">
                    <i class="fas fa-project-diagram text-purple-600 mr-3"></i>
                    算法流程
                </h2>
                <div class="mermaid">
                    graph TD
                        A[开始] --> B[选择基准元素]
                        B --> C[分区操作]
                        C --> D{左子数组是否为空?}
                        D -->|否| E[递归排序左子数组]
                        D -->|是| F[跳过左子数组]
                        E --> G{右子数组是否为空?}
                        F --> G
                        G -->|否| H[递归排序右子数组]
                        G -->|是| I[跳过右子数组]
                        H --> J[合并结果]
                        I --> J
                        J --> K[结束]
                        
                        style A fill:#667eea,stroke:#333,stroke-width:2px,color:#fff
                        style K fill:#667eea,stroke:#333,stroke-width:2px,color:#fff
                        style B fill:#764ba2,stroke:#333,stroke-width:2px,color:#fff
                        style C fill:#764ba2,stroke:#333,stroke-width:2px,color:#fff
                </div>
            </div>
        </section>

        <!-- 代码实现 -->
        <section class="mb-16 fade-in">
            <h2 class="text-3xl font-bold mb-8 text-gray-800 flex items-center">
                <i class="fas fa-code text-purple-600 mr-3"></i>
                Java 实现
            </h2>
            <div class="code-container">
                <div class="code-header">
                    <div class="code-dots">
                        <div class="dot dot-red"></div>
                        <div class="dot dot-yellow"></div>
                        <div class="dot dot-green"></div>
                    </div>
                    <span class="text-gray-400 text-sm">QuickSort.java</span>
                </div>
                <pre><code><span class="keyword">public class</span> <span class="type">QuickSort</span> {
    <span class="comment">/**
     * 快速排序主方法
     * @param nums 待排序数组
     * @return 排序后的数组
     */</span>
    <span class="keyword">public</span> <span class="type">int[]</span> <span class="function">quickSort</span>(<span class="type">int[]</span> nums) {
        <span class="comment">// 调用递归排序方法</span>
        <span class="function">quickSortRecursive</span>(nums, <span class="number">0</span>, nums.length - <span class="number">1</span>);
        <span class="keyword">return</span> nums;
    }
    
    <span class="comment">/**
     * 递归实现快速排序
     * @param nums 待排序数组
     * @param left 左边界
     * @param right 右边界
     */</span>
    <span class="keyword">private void</span> <span class="function">quickSortRecursive</span>(<span class="type">int[]</span> nums, <span class="type">int</span> left, <span class="type">int</span> right) {
        <span class="comment">// 递归终止条件：区间长度为1或更小</span>
        <span class="keyword">if</span> (left < right) {
            <span class="comment">// 获取分区点</span>
            <span class="type">int</span> pivotIndex = <span class="function">partition</span>(nums, left, right);
            
            <span class="comment">// 递归排序左半部分</span>
            <span class="function">quickSortRecursive</span>(nums, left, pivotIndex - <span class="number">1</span>);
            
            <span class="comment">// 递归排序右半部分</span>
            <span class="function">quickSortRecursive</span>(nums, pivotIndex + <span class="number">1</span>, right);
        }
    }
    
    <span class="comment">/**
     * 分区函数，将数组分为小于和大于基准的两部分
     * @param nums 待分区数组
     * @param left 左边界
     * @param right 右边界
     * @return 基准元素的最终位置
     */</span>
    <span class="keyword">private int</span> <span class="function">partition</span>(<span class="type">int[]</span> nums, <span class="type">int</span> left, <span class="type">int</span> right) {
        <span class="comment">// 选择最右边的元素作为基准</span>
        <span class="type">int</span> pivot = nums[right];
        
        <span class="comment">// i表示小于等于基准的元素的最后位置</span>
        <span class="type">int</span> i = left - <span class="number">1</span>;
        
        <span class="comment">// 遍历区间内的所有元素（除了基准）</span>
        <span class="keyword">for</span> (<span class="type">int</span> j = left; j < right; j++) {
            <span class="comment">// 如果当前元素小于等于基准，将其交换到前面</span>
            <span class="keyword">if</span> (nums[j] <= pivot) {
                i++;
                <span class="comment">// 交换元素</span>
                <span class="function">swap</span>(nums, i, j);
            }
        }
        
        <span class="comment">// 将基准元素放到正确的位置</span>
        <span class="function">swap</span>(nums, i + <span class="number">1</span>, right);
        
        <span class="comment">// 返回基准元素的位置</span>
        <span class="keyword">return</span> i + <span class="number">1</span>;
    }
    
    <span class="comment">/**
     * 交换数组中的两个元素
     * @param nums 数组
     * @param i 第一个元素的索引
     * @param j 第二个元素的索引
     */</span>
    <span class="keyword">private void</span> <span class="function">swap</span>(<span class="type">int[]</span> nums, <span class="type">int</span>